import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        System.out.println("before: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("after: " + Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        int len = arr.length;
        quickSortCore(arr, 0, len - 1);
    }

    public static void quickSortCore(int[] arr, int l, int r) {
        if (l > r) return;
        int mid = partition(arr, l, r);
        quickSortCore(arr, l, mid - 1);
        quickSortCore(arr, mid + 1, r);
    }

    public static int partition(int[] arr, int l, int r) {
        int mid = l + (int) (Math.random() * (r - l + 1));
        swap(arr, mid, r);
        int st = l - 1;
        while (l < r) {
            if (arr[l] < arr[r]) {
                swap(arr, ++st, l);
            }
            l++;
        }
        swap(arr, ++st, r);
        return st;
    }

    public static void swap(int[] arr, int l, int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
}
